home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / gen / SkipSet.ccP < prev    next >
Text File  |  1992-04-14  |  8KB  |  396 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1991 Free Software Foundation
  4.  
  5. This file is part of the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /*
  19.  * Sets implemented via William Pugh SkipList algorithms.
  20.  * CACM, June 1990, p 668-676.
  21.  *
  22.  */
  23.  
  24. #include <stream.h>
  25. #include <time.h>
  26.  
  27. #include "<T>.SkipSet.h"
  28.  
  29. MLCG* <T>SkipSet::gen = 0;
  30. int <T>SkipSetinit::count = 0;
  31.  
  32. static int countbits(long bits)
  33. {
  34.    int n = 0;
  35.    while(bits>>=1L) n++;
  36.    return n;
  37. }
  38.  
  39. <T>SkipSet::<T>SkipSet(long size)
  40. : level(0),
  41.   header(new <T>SkipSetNode (countbits(size)+1)),
  42.   max_levels (countbits(size)+1),
  43.   random_bits(gen->asLong()),
  44.   randoms_left(BITS_IN_RANDOM / 2)
  45. {
  46.   <T>SkipSetNodePtr *buffer_start = header->forward;
  47.   <T>SkipSetNodePtr *trav = &header->forward[max_levels];
  48.   
  49.   count = 0;
  50.   while (trav > buffer_start)
  51.     *--trav = (<T>SkipSetNodePtr) header;
  52. }
  53.  
  54. <T>SkipSet::<T>SkipSet(<T>SkipSet& b)
  55. : level (0),
  56.   header (new <T>SkipSetNode (b.max_levels)),
  57.   max_levels (b.max_levels),
  58.   random_bits (gen->asLong()),
  59.   randoms_left (BITS_IN_RANDOM / 2)
  60. {
  61.   <T>SkipSetNodePtr *buffer_start = header->forward;
  62.   <T>SkipSetNodePtr *trav = &header->forward[max_levels];
  63.   
  64.   count = 0;
  65.   
  66.    while (trav > buffer_start)
  67.      *--trav = (<T>SkipSetNodePtr)header;
  68.   
  69.   for (<T>SkipSetNodePtr t = b.leftmost(); t; t = b.succ(t))
  70.       add(t->item);
  71. }
  72.  
  73. /* relationals */
  74.  
  75. int <T>SkipSet::operator == (<T>SkipSet& y)
  76. {
  77.   if (count != y.count)
  78.     return 0;
  79.   else
  80.   {
  81.     <T>SkipSetNodePtr t = leftmost();
  82.     <T>SkipSetNodePtr u = y.leftmost();
  83.     for (;;)
  84.     {
  85.       if (t == 0)
  86.         return 1;
  87.       else if (!<T>EQ(t->item, u->item))
  88.         return 0;
  89.       else
  90.       {
  91.         t = succ(t);
  92.         u = y.succ(u);
  93.       }
  94.     }
  95.   }
  96. }
  97.  
  98. int <T>SkipSet::operator <= (<T>SkipSet& y)
  99. {
  100.   if (count > y.count)
  101.     return 0;
  102.   else
  103.   {
  104.     <T>SkipSetNodePtr t = leftmost();
  105.     <T>SkipSetNodePtr u = y.leftmost();
  106.     for (;;)
  107.     {
  108.       if (t == 0)
  109.         return 1;
  110.       else if (u == 0)
  111.         return 0;
  112.       int cmp = <T>CMP(t->item, u->item);
  113.       if (cmp == 0)
  114.       {
  115.         t = succ(t);
  116.         u = y.succ(u);
  117.       }
  118.       else if (cmp < 0)
  119.         return 0;
  120.       else
  121.         u = y.succ(u);
  122.     }
  123.   }
  124. }
  125.  
  126.  
  127. void <T>SkipSet::operator |=(<T>SkipSet& y)
  128. {
  129.   if (&y == this) return;
  130.   <T>SkipSetNodePtr u = y.leftmost();
  131.   while (u != 0)
  132.   {
  133.     add(u->item);
  134.     u = y.succ(u);
  135.   }
  136. }
  137.  
  138. void <T>SkipSet::operator &= (<T>SkipSet& y)
  139. {
  140.   if (y.count == 0)
  141.     clear();
  142.   else if (&y != this && count != 0)
  143.   {
  144.     <T>SkipSetNodePtr t = leftmost();
  145.     while (t != 0)
  146.     {
  147.       <T>SkipSetNodePtr s = succ(t);
  148.       if (y.seek(t->item) == 0) del(t->item);
  149.       t = s;
  150.     }
  151.   }
  152. }
  153.  
  154.  
  155. void <T>SkipSet::operator -=(<T>SkipSet& y)
  156. {
  157.   if (&y == this)
  158.     clear();
  159.   else if (y.count != 0)
  160.   {
  161.     <T>SkipSetNodePtr t = leftmost();
  162.     while (t != 0)
  163.     {
  164.       <T>SkipSetNodePtr s = succ(t);
  165.       if (y.seek(t->item) != 0) del(t->item);
  166.       t = s;
  167.     }
  168.   }
  169. }
  170.  
  171. Pix <T>SkipSet::add (<T&> i)
  172. {
  173.   <T>SkipSetNodePtr *update = new <T>SkipSetNodePtr[max_levels+1];
  174.   <T>SkipSetNodePtr curr = (<T>SkipSetNodePtr) this->header;
  175.   int   l = level;
  176.   <T>SkipSetNodePtr temp;
  177.   
  178.   do
  179.   {
  180.     while ((temp = curr->forward[l])!=header &&
  181.        <T>CMP(temp->item, i) < 0)
  182.       curr = temp;
  183.     update[l] = curr;
  184.   } 
  185.   while (--l >= 0);
  186.   
  187.   if (temp != header && <T>CMP(temp->item, i) == 0)
  188.     return Pix(temp);
  189.  
  190.   if ((l = random_level ()) > level)
  191.   {
  192.     l = ++level;
  193.     update[l] = (<T>SkipSetNodePtr)header;
  194.   };
  195.  
  196.   temp = new <T>RealSkipSetNode (i, l);
  197.   <T>SkipSetNodePtr *temp_forward = temp->forward;
  198.   
  199.   do
  200.   {
  201.     <T>SkipSetNodePtr *curr_forward = update[l]->forward;
  202.     
  203.     temp_forward[l] = curr_forward[l];
  204.     curr_forward[l] = temp;
  205.   } 
  206.   while (--l >= 0);
  207.  
  208.   count++;
  209.   delete update;
  210.   return Pix(temp);
  211. }
  212.  
  213. void <T>SkipSet::del(<T&> key)
  214. {
  215.   
  216.   int   l = level;
  217.   int   curr_level = level;
  218.   <T>SkipSetNodePtr *update = new <T>SkipSetNodePtr[max_levels+1];
  219.   <T>SkipSetNodePtr curr = (<T>SkipSetNodePtr)header;
  220.   <T>SkipSetNodePtr temp;
  221.   
  222.   do
  223.   {
  224.     while ((temp = curr->forward[l])!=header
  225.        && <T>CMP(temp->item,key) < 0)
  226.       curr = temp;
  227.     update[l] = curr;
  228.   } 
  229.   while (--l >= 0);
  230.   
  231.   if (<T>CMP(temp->item,key)==0)
  232.   {
  233.     <T>SkipSetNodePtr *temp_forward = temp->forward;
  234.     
  235.     for (l = 0;
  236.      l <= curr_level && (curr = update[l])->forward[l] == temp;
  237.      l++)
  238.       curr->forward[l] = temp_forward[l];
  239.     
  240.     delete temp;
  241.     
  242.     <T>SkipSetNodePtr *forward = header->forward;
  243.     
  244.     while (forward[curr_level]==header && curr_level > 0)
  245.       curr_level--;
  246.  
  247.     level = curr_level;
  248.     count--;
  249.     delete update;
  250.     return;
  251.   }
  252. }
  253.  
  254. <T>SkipSetNodePtr <T>SkipSet::rightmost()
  255. {
  256.   <T>SkipSetNodePtr temp;
  257.   <T>SkipSetNode*   curr = header;
  258.   int l = level;
  259.   
  260.   do
  261.     while ((temp = curr->forward[l])!=header)
  262.       curr = temp;
  263.   while (--l >= 0);
  264.   
  265.   return temp==header ? 0 : temp;
  266. }
  267.  
  268. <T>SkipSetNodePtr <T>SkipSet::pred(<T>SkipSetNodePtr t)
  269. {
  270.   <T>SkipSetNodePtr temp, curr = (<T>SkipSetNodePtr) header;
  271.   int l = level;
  272.   
  273.   do
  274.     while ((temp = curr->forward[l])!=t)
  275.       curr = temp;
  276.   while (--l >= 0);
  277.   
  278.   return curr == header ? 0 : curr;
  279. }
  280.  
  281. void <T>SkipSet::_kill()
  282. {
  283.   <T>SkipSetNode *p = this->header->forward[0];
  284.   
  285.   while (p != header)
  286.   {
  287.     <T>SkipSetNodePtr q = p->forward[0];
  288.     delete p;
  289.     p = q;
  290.   }
  291. }
  292.  
  293. void <T>SkipSet::clear()
  294. {
  295.   <T>SkipSetNodePtr *buffer_start = header->forward;
  296.   <T>SkipSetNodePtr *trav = &header->forward[level+1];
  297.   _kill();
  298.   count = 0;
  299.     
  300.   while (trav > buffer_start)
  301.     *--trav = (<T>SkipSetNodePtr)header;
  302. }
  303.  
  304. Pix <T>SkipSet::seek(<T&> key)
  305. {
  306.   <T>SkipSetNodePtr temp;
  307.   <T>SkipSetNode *curr  = header;
  308.   int   l = level;
  309.   
  310.   do
  311.   {
  312.     while ((temp = curr->forward[l])!=header &&
  313.        <T>CMP(temp->item, key) < 0)
  314.       curr = temp;
  315.   }
  316.   while (--l >= 0);
  317.   
  318.   if (<T>CMP(temp->item, key) != 0)
  319.     return 0;
  320.   else
  321.   {
  322.     return Pix(temp);
  323.   }
  324. }
  325.  
  326.  
  327. /*
  328.  * random function for probabilistic balancing
  329.  *
  330.  * Hardwired for p = .25.  Not too flexible,
  331.  * but fast.  Changing this would require a constructor
  332.  * that would accept a different value for p, etc.
  333.  * Perhaps someone else would like to implement this?
  334.  *
  335.  */
  336. int <T>SkipSet::random_level (void)
  337. {
  338.   int rlevel = 0;
  339.   int b;
  340.   
  341.   do
  342.   {
  343.     b = random_bits & 3L;
  344.     if (!b)
  345.       rlevel++;
  346.     random_bits >>= 2;
  347.     if (--randoms_left == 0)
  348.     {
  349.       random_bits = gen->asLong();
  350.       randoms_left = BITS_IN_RANDOM / 2;
  351.     };
  352.   } 
  353.   while (!b);
  354.   
  355.   return rlevel > max_levels ? max_levels : rlevel;
  356. }
  357.  
  358. int <T>SkipSet::OK()
  359. {
  360.   int v = 1;
  361.   if (header == 0) 
  362.     v = 0;
  363.   else
  364.   {
  365.     int n = 0;
  366.     <T>SkipSetNodePtr trail = leftmost();
  367.     <T>SkipSetNodePtr t = 0;
  368.     if (trail) t = succ(trail);
  369.     if (t) n++;
  370.     while (t != 0)
  371.     {
  372.       ++n;
  373.       v &= <T>CMP(trail->item, t->item) < 0;
  374.       trail = t;
  375.       t = succ(t);
  376.     }
  377.     v &= n == count;
  378.   }
  379.   if (!v) error("invariant failure");
  380.   return v;
  381. }
  382.  
  383. <T>SkipSetinit::<T>SkipSetinit()
  384. {
  385.     if (!count)
  386.     <T>SkipSet::gen = new MLCG(time(0));
  387.     count++;
  388. }
  389.  
  390. <T>SkipSetinit::~<T>SkipSetinit()
  391. {
  392.     count--;
  393.     if (!count)
  394.     delete <T>SkipSet::gen;
  395. }
  396.